package graph;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class UnDirectGraph extends Graph {

	@Override
	public boolean innerGraph(int[][] matrix, int vertex) {
		int[] visitedVertex = new int[matrix.length];
		visitedVertex[vertex]++;
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(vertex);
		while (!stack.isEmpty()) {
			vertex = stack.pop();
			for (int i = 0; i < matrix.length; i++) {
				if (matrix[vertex][i] > 0 && visitedVertex[i] == 0) {
					stack.push(i);
					visitedVertex[i]++;
				}
			}
		}
		for (int i = 0; i < visitedVertex.length; i++) {
			if (visitedVertex[i] != 1) {
				return false;
			}
		}
		return true;
	}

	@Override
	public int innerGraphElement(int[][] matrix, int vertex, int element) {

		int[] visitedVertex = new int[matrix.length];
		visitedVertex[vertex]++;
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(vertex);
		while (!stack.isEmpty()) {
			vertex = stack.pop();
			for (int i = 0; i < matrix.length; i++) {
				if (matrix[vertex][i] > 0 && visitedVertex[i] == 0) {
					stack.push(i);
					visitedVertex[i]++;
				}
			}
		}
		element++;
		for (int i = 0; i < visitedVertex.length; i++) {
			if (visitedVertex[i] == 0) {
				return innerGraphElement(matrix, i, element);
			}
		}
		return element;
	}

	@Override
	public int countEdgeGraph(int[][] matrix) {
		int count = 0;
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix.length; j++) {
				count += matrix[i][j];
			}
		}
		return count / 2;
	}

	@Override
	public boolean checkEuler(int[][] matrix, int node) {
		if(innerGraph(matrix, node) && checkEvenLevelOfVertex(matrix)){
			return true;
		}
		return false;
	}
	/**
	 * kiểm tra bậc chẵn của các đỉnh của đồ thị
	 * @param matrix
	 * @return
	 */
	private boolean checkEvenLevelOfVertex(int[][] matrix){
		for (int i = 0; i < matrix.length; i++) {
			int sum=0;
			for (int j = 0; j < matrix.length; j++) {
				sum+=matrix[i][j];
			}
			if(sum%2!=0){
				return false;
			}
		}
		return true;
	}
	
	public boolean checkEuler1(int[][] matrix, int node) {
		Stack<Integer> stack = new Stack<Integer>();
		int[] visitedVertex = new int[matrix.length];
		visitedVertex[node]++;
		stack.push(node);
		int vertex = -1;
		boolean isCrossAllEdge = false;
		while (vertex != node && isCrossAllEdge==false) {
			if(vertex==-1){
				vertex=node;
			}
			for (int i = 0; i < matrix.length; i++) {
				if (matrix[vertex][i] != 0 && i!=vertex) {
					stack.push(i);
					if (visitedVertex[i] == 0) {
						visitedVertex[i]++;
					}
					if (matrix[vertex][i] != 0) {
						matrix[vertex][i]--;
					}
					if (matrix[vertex][i] != 0) {
						matrix[i][vertex]--;
					}
					vertex = i;
					break;
				}
			}
			boolean checkAllEdge = true;
			for (int i = 0; i < matrix.length; i++) {
				for (int j = 0; j < matrix.length; j++) {
					if (matrix[i][j] != 0) {
						checkAllEdge = false;
						break;
					}
				}
			}
			if (!checkAllEdge) {
				isCrossAllEdge = false;
			} else {
				isCrossAllEdge = true;
			}
		}
		return true;
	}

	/**
	 * tìm độ lệnh tâm giữa 2 đỉnh trong cây
	 * @param matrix
	 * @param u
	 * @param v
	 * @return
	 */
	
	public int findEccentricity(int[][] matrix, int u, int v) {
		if (u == v)
			return 0;
		Stack<Integer> stack = new Stack<Integer>();
		int[] visitedVertex = new int[matrix.length];
		visitedVertex[u]++;
		stack.push(u);
		int vertex = u;
		int len = 0;
		boolean next = false;

		loops1: while (!stack.isEmpty()) {
			next = false;
			loops2: for (int i = 0; i < matrix.length; i++) {
				if (matrix[vertex][i] != 0 && visitedVertex[i] == 0) {
					visitedVertex[i]++;
					stack.push(i);
					len++;
					vertex = i;
					next = true;
					if (i == v) {
						break loops1;
					} else {
						break loops2;
					}
				}
			}
			if (next == false) {
				boolean checkCrossAllVertex = true;
				for (int i = 0; i < visitedVertex.length; i++) {
					if (visitedVertex[i] != 1) {
						checkCrossAllVertex = false;
					}
				}
				if (checkCrossAllVertex) {
					return len;
				} else {
					vertex = stack.pop();
					len--;
				}
			}
		}
		return len;
	}

	/**
	 * độ lệnh tâm lớn nhất của một đỉnh trong cây
	 * @param matrix
	 * @param u
	 * @return
	 */
	public int eccentricityVertex(int[][] matrix, int u) {
		int max = -1;
		int temp = 0;
		for (int i = 0; i < matrix.length; i++) {
			if (i == u) {
				continue;
			}
			temp = findEccentricity(matrix, u, i);
			if (max == -1) {
				max = temp;
			} else if (max < temp) {
				max = temp;
			}
		}
		return max;
	}

	@Override
	public boolean checkPathBetweenTwoVertex(int[][] matrix, int u, int v) {
		if (u == v)
			return true;
		Stack<Integer> stack = new Stack<Integer>();
		int[] visitedVertex = new int[matrix.length];
		visitedVertex[u]++;
		stack.push(u);
		int vertex = u;
		boolean next = false;
		loops1: while (!stack.isEmpty()) {
			next = false;
			loops2: for (int i = 0; i < matrix.length; i++) {
				if (matrix[vertex][i] != 0 && visitedVertex[i] == 0) {
					visitedVertex[i]++;
					stack.push(i);
					vertex = i;
					next = true;
					if (i == v) {
						return true;
					} else {
						break loops2;
					}
				}
			}
			if (next == false) {
				boolean checkCrossAllVertex = true;
				for (int i = 0; i < visitedVertex.length; i++) {
					if (visitedVertex[i] != 1) {
						checkCrossAllVertex = false;
					}
				}
				if (checkCrossAllVertex) {
					return false;
				} else {
					vertex = stack.pop();
				}
			}
		}
		return false;
	}

	@Override
	public int countLevelOfVertex(int[][] matrix, int vertex) {
		int count = 0;
		for (int i = 0; i < matrix.length; i++) {
			count += matrix[vertex][i];
		}
		return count;
	}

	public static void main(String[] args) throws IOException {
		Graph test = new UnDirectGraph();
		//String path = "uneuler.txt";
		//String path = "euler.txt";
		//String path = "graph.txt";
		String path = "printpath.txt";
		// String path = "tree.txt";
		test.printAllPathBetweenTwoVertex(test.readFile(path),0,2);
		// test.printMatrix(test.readFile(path));
	}

	@Override
	public boolean checkTree(int[][] matrix) {
		if (innerGraph(matrix, 0)
				&& countEdgeGraph(matrix) == matrix.length - 1) {
			return true;
		}
		return false;
	}

	@Override
	public void printAllPathBetweenTwoVertex(int[][] matrix, int u, int v) {
		if(!checkPathBetweenTwoVertex(matrix,u,v)){
			System.out.println("Khong co duong di");
		}
		System.out.println("Duong di la:");
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(u);
		List<Integer> checkAllVertexNext = new ArrayList<Integer>();
		for(int i=0;i<matrix.length;i++){
			if(matrix[u][i]!=0 && !stack.contains(i)){
				checkAllVertexNext.add(i);
			}
		}
		for(int i=0;i<checkAllVertexNext.size();i++){
			int temp = checkAllVertexNext.get(i);
			stack.push(temp);
			if(temp==v){
				printPath(stack);
			}else{
				printAllPathBetweenTwoVertex(matrix,temp,v,stack);
			}
			stack.pop();
		}
		
	}

	private void printAllPathBetweenTwoVertex(int[][] matrix, int u, int v,
			Stack<Integer> stack) {
		List<Integer> checkAllVertexNext = new ArrayList<Integer>();
		for(int i=0;i<matrix.length;i++){
			if(matrix[u][i]!=0 && !stack.contains(i)){
				checkAllVertexNext.add(i);
			}
		}
		for(int i=0;i<checkAllVertexNext.size();i++){
			int temp = checkAllVertexNext.get(i);
			stack.push(temp);
			if(temp==v){
				printPath(stack);
			}else{
				printAllPathBetweenTwoVertex(matrix,temp,v,stack);
			}
			stack.pop();
		}
		
		
	}

	private void printPath(Stack<Integer> stack) {
		for(int i=0;i<stack.size();i++){
			System.out.print(stack.get(i)+" ");
		}
		System.out.println();
	}

}
